package basic.courseLearn13.clueBinaryTree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.junit.Test;

//线索二叉树的遍历
public class OrderTraversal {

    @Test
    public void test() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);

        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.left = new Node(8);

        this.preOrder(root);
        System.out.println();
        this.inOrder(root);
        System.out.println();
        this.reversePrintRight(root);
        System.out.println();
        this.postOrder(root);

    }

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    private class Node{
        int val;
        Node left, right;

        public Node(int val) {
            this.val = val;
        }
    }


    //先序遍历：第一次出现输出
    public void preOrder(Node root) {
        //1. 定义临时变量
        Node tempNode = root;
        //2. 递归
        while (true) {
            //2.1 左子树存在
            if (tempNode.left!= null) {
                //2.1.1 找到左子树得最右节点
                Node rightMost = findLeftTreeRightMost(tempNode);
                //2.1.2 最右节点无右孩子
                if (rightMost.right == null){
                    System.out.print(tempNode.val + " ");
                    rightMost.right = tempNode;
                    tempNode = tempNode.left;
                }else{ //最右节点有右孩子
                    tempNode = tempNode.right;
                    rightMost.right = null;
                }
            }else if (tempNode.right != null) { //右子树存在
                System.out.print(tempNode.val + " ");
                tempNode = tempNode.right;
            }else { //左右子树都不存在
                System.out.print(tempNode.val + " ");
                break;
            }
        }
    }


    //中序遍历：最后一次出现输出
    public void inOrder(Node root) {
        //1. 定义临时变量
        Node tempNode = root;
        //2. 递归
        while (true) {
            //2.1 左子树存在
            if (tempNode.left!= null) {
                //2.1.1 找到左子树得最右节点
                Node rightMost = findLeftTreeRightMost(tempNode);
                //2.1.2 最右节点无右孩子
                if (rightMost.right == null){
                    rightMost.right = tempNode;
                    tempNode = tempNode.left;
                }else{ //最右节点有右孩子
                    System.out.print(tempNode.val+" ");
                    tempNode = tempNode.right;
                    rightMost.right = null;
                }
            }else if (tempNode.right != null) { //右子树存在
                System.out.print(tempNode.val+" ");
                tempNode = tempNode.right;
            }else { //左右子树都不存在
                System.out.print(tempNode.val+" ");
                break;
            }
        }
    }


    //后序遍历：第二次出现逆序打印左子树得有边界，最后在打印树的右边界
    public void postOrder(Node root) {
        //1. 定义临时变量
        Node tempNode = root;
        //2. 递归
        while (true) {
            //2.1 左子树存在
            if (tempNode.left!= null) {
                //2.1.1 找到左子树得最右节点
                Node rightMost = findLeftTreeRightMost(tempNode);
                //2.1.2 最右节点无右孩子
                if (rightMost.right == null){
                    rightMost.right = tempNode;
                    tempNode = tempNode.left;
                }else{ //最右节点有右孩子
                    rightMost.right = null;
                    reversePrintRight(tempNode.left);
                    tempNode = tempNode.right;
                }
            }else if (tempNode.right != null) { //右子树存在
                tempNode = tempNode.right;
            }else { //左右子树都不存在
                break;
            }
        }
        reversePrintRight(root);
    }


    //查找左子树的最右节点（存在左子树），不能成循环
    public Node findLeftTreeRightMost(Node root) {
        Node tempNode = root.left;
        while (tempNode.right != null && tempNode.right != root) {
            tempNode = tempNode.right;
        }
        return tempNode;
    }

    //逆序打印右边界，空间复杂度O(1)
    public void reversePrintRight(Node root) {
        //1. 判断特殊情况
        if(root.right == null){
            System.out.print(root.val+" ");
            return;
        }
        //2. 定义快慢指针
        Node fast = root.right;
        Node slow = root;
        slow.right = null;
        //3. 修改链表--逆序
        while (fast != null){
            Node temp = fast.right;
            fast.right = slow;
            slow = fast;
            fast = temp;
        }
        //4. 打印链表
        while (slow != null){
            Node temp = slow.right;
            System.out.print(slow.val+" ");
            slow.right = fast;
            fast = slow;
            slow = temp;
        }

    }
}
